package demo1;


import javax.print.attribute.standard.NumberUpSupported;

public class MyQueue {
    //实现队列
    //通过链表实现队列，
    //如果通过单链表—头插,尾删时间复杂度为O(n)，
    // 采取(尾插，头删)时间复杂度为O(1)
    //采用双链表实现队列
    static  class  ListNode{
        //设定一个节点对象
          int data ;
          ListNode prev ;
          ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }
    //反是涉及到链表的使用就必须有指针
    ListNode first;   //创建指向队列首部的标记
    ListNode last;   //创建指向队列尾部的标记


    //队列的方法：
        //入队列
        public void offer(int data) {
            //采用头插法
            ListNode cur = new ListNode(data);
            if(isEmpty()){
                first = last = cur;
            }else {
                cur.next = first;
                first.prev = cur;
                first = cur;
            }

        }
        //出队列
        public int poll() {
            try {
                if (isEmpty()) {
                    throw new EmptyException("空队列异常！！！");
                }
            }catch (EmptyException e){
                e.printStackTrace();
            }
            int ret = last.data;
            last = last.prev;
            last.next = null;  // 删除尾结点
            return ret;
        }
        //获取队头元素 但是不删除
        public int peek() {
            //获取队头元素
            try {
                if (isEmpty()) {
                    throw new EmptyException("空队列异常！！！");
                }
            }catch (EmptyException e){
                e.printStackTrace();
            }
            return last.data;
        }
        //判空
        //判断头标记是否为空
        public boolean isEmpty() {
            //不采用usedsize的方式
            return  first ==null;

        }
        //获取队列元素个数
        public int size(){
              //遍历整个链表
            ListNode cur = first;
            int count = 0 ;
            while (cur!=null){
                count++;
                cur = cur.next;
            }
            return  count;
        }


}
